package cn.edu.ncepu;

import java.util.*;

/**
 * 置换树节点类
 */
class Node {
    private Integer value;
    private Node parent;
    private List<Node> children;

    public Node() {
        this.children = new ArrayList<>();
    }

    // Getter & Setter for value
    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    // Getter & Setter for parent
    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    // Getter & Setter for children
    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    /**
     * 查找父节点和前驱节点
     * @param e 目标值
     * @return 数组 [p, sib]，p为父节点，sib为前驱节点
     */
    public Node[] findParent(Integer e) {
        Node x = this;
        Node prev = x;
        while (x.getValue() >= e) {
            prev = x;
            x = x.getParent();
            // 防止根节点parent为null导致空指针
            if (x == null) break;
        }
        return new Node[]{x, prev};
    }

    @Override
    public String toString() {
        return value != null ? value.toString() : "null";
    }
}

/**
 * 置换树类
 */
public class PermutationTree {
    private Node root;

    public PermutationTree() {
        Node rootNode = new Node();
        rootNode.setValue(0);
        this.root = rootNode;
    }

    // Getter & Setter for root
    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    /**
     * 根据数组构建置换树
     * @param array 输入数组
     */
    public void of(List<Integer> array) {
        Map<Integer, Node> nodeMap = new HashMap<>();
        for (int i = 0; i < array.size(); i++) {
            Integer e = array.get(i);
            Node node = new Node();
            node.setValue(e);
            nodeMap.put(e, node);

            if (i > 0) {
                Integer prevVal = array.get(i - 1);
                Node prevNode = nodeMap.get(prevVal);

                if (e > prevVal) {
                    // 作为子节点添加
                    prevNode.getChildren().add(node);
                    node.setParent(prevNode);
                } else {
                    // 查找父节点，作为左兄弟添加
                    Node[] parentResult = prevNode.findParent(e);
                    Node p = parentResult[0];
                    // 若p为null，使用根节点
                    if (p == null) {
                        p = this.root;
                    }
                    List<Node> children = p.getChildren();
                    int index = indexOf(children, e);
                    children.add(index, node);
                    node.setParent(p);
                }
            } else {
                // 第一个元素，添加到根节点的子节点
                this.root.getChildren().add(node);
                node.setParent(this.root);
            }
        }
    }

    /**
     * 生成DOT语言字符串（用于可视化树结构）
     * @return DOT格式字符串
     */
    public String toDotString() {
        StringBuilder sb = new StringBuilder();
        sb.append("digraph {\n");
        List<Node> stack = new ArrayList<>();
        stack.add(this.root);
        sb.append(String.format("\tn%s[label=\"%s\"]\n", root.getValue(), root.getValue()));

        while (!stack.isEmpty()) {
            Node v = stack.remove(stack.size() - 1); // 模拟Python的pop()
            for (Node x : v.getChildren()) {
                sb.append(String.format("\tn%s[label=\"%s\"]\n", x.getValue(), x.getValue()));
                sb.append(String.format("\tn%s -> n%s\n", v.getValue(), x.getValue()));
                stack.add(x);
            }
        }
        sb.append("}\n");
        return sb.toString();
    }

    /**
     * 将树转换为排列数组
     * @return 排列数组
     */
    public List<Integer> toPermutation() {
        List<Integer> array = new ArrayList<>();
        List<Node> stack = new ArrayList<>();
        stack.add(this.root);

        while (!stack.isEmpty()) {
            Node v = stack.remove(stack.size() - 1);
            if (v.getValue() != 0) { // 跳过根节点（值为0）
                array.add(v.getValue());
            }
            // 子节点入栈（保持顺序与Python一致）
            for (Node x : v.getChildren()) {
                stack.add(x);
            }
        }
        return array;
    }

    /**
     * 二分查找节点列表中目标值的插入索引
     * @param children 节点列表
     * @param e 目标值
     * @return 插入索引
     */
    private int indexOf(List<Node> children, Integer e) {
        int start = 0;
        int end = children.size() - 1;
        // 处理空列表或单元素列表
        if (children.isEmpty()) return 0;
        if (start == end) return start;

        while (start != end) {
            int mid = (start + end) / 2;
            Integer midVal = children.get(mid).getValue();
            if (e < midVal) {
                end = mid;
            } else if (e.equals(midVal)) {
                return mid;
            } else {
                start = mid;
            }
            // 防止死循环（当start和end相邻时）
            if (end - start == 1) {
                break;
            }
        }
        // 最后判断相邻的两个元素
        return e < children.get(start).getValue() ? start : end;
    }

    public static void main(String[] args) {
        PermutationTree tree = new PermutationTree();
        List<Integer> array = Arrays.asList(3, 4, 2, 1);
        tree.of(array);
        System.out.println(tree.toDotString());
        System.out.println(tree.toPermutation());
    }
}